class Solution:
    """
    这个是参考网上答案写的,让自己想确实不容易想到后面的规划到底怎么规划
    dp[i][j] 表示戳破i, j中间所有气球的最大收益(不包含端点)
    """
    def maxCoins(self, nums: list) -> int:
        i = 0
        while i < len(nums):
            if nums[i] == 0:
                nums.pop(i)
            else:
                i += 1
        nums = [1] + nums + [1]
        length = len(nums)
        dp = [[0] * length for i in range(length - 1)]
        for j in range(2, length):
            for i in range(j-2, -1, -1):
                for k in range(i+1, j):
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
            for line in dp:
                print(line)
            print("---------------------------")
        return dp[0][-1]


a = Solution()
print(a.maxCoins([3, 1, 5, 8]))  # 167
print(a.maxCoins([1,6,8,3,4,6,4,7,9,8,0,6,2,8]))  # 3376
print(a.maxCoins([8,3,4,3,5,0,5,6,6,2,8,5,6,2,3,8,3,5,1,0,2]))  # 3394
